package com.love.labuladong.sort.mergesort;

/**
 * 归并排序
 */
public class MergeSort {


    public static void sort(int[] arr){
        int r = arr.length - 1;
        mergeSort(arr,0,r);
    }

    /**
     * 定义 ： 在 arr[l ... r] 上从小到大排序
     * @param arr
     * @param l
     * @param r
     */
    public static void mergeSort(int[] arr,int l,int r){
        // l == r ：表示到达同一个数了，同一个数无需比较排序，直接返回
        if(l == r){
            return;
        }
        // 中点
        int mid = l + ((r - l) >>> 1);
        // 排序左半边
        mergeSort(arr,l,mid);
        // 排序右半边
        mergeSort(arr,mid + 1,r);
        // 如果一微观的视角 mergeSort 是将 arr[] 分为到 单个数值，然后 merge 进行比较排序，然后触底反弹
        // 把左半边(已经排好序)和右半边(已经排好序)整体排序
        merge(arr,l,mid,r);
    }


    /**
     * 归并排序的 排 与 并
     *
     * 将 arr[start,mid] 和 arr[mid + 1,end] 的数据 整体排序
     *
     * @param arr
     * @param start
     * @param mid
     * @param end
     */
    public static void merge(int[] arr,int start,int mid,int end){
        // 创建相同长度的临时数组
        int[] temp = new int[end - start + 1];
        // 双指针
        int l = start;
        int r = mid + 1;
        int i = 0;
        // 在 l, r 都不越界的位置，谁小取谁
        while (l <= mid && r <= end){
            temp[i++] = arr[l] > arr[r] ? arr[r++] : arr[l++];
        }

        //走出第一个while  表示 第一个 while 中， l 或 r 其中一个越界了，但是不知道到底谁越界，所以下面两个while接分别检查谁越界了，
        // 下面while只会走一个

        while (l <= mid){
            temp[i++] = arr[l++];
        }

        while (r <= end){
            temp[i++] = arr[r++];
        }

        // 把 arr[start ... end] 的数值更新
        for (int k : temp) {
            arr[start++] = k;
        }
    }


    public static void main(String[] args) {

//        int[] arr = {2,3,1,4,9,4,3,5,2,5};
//
//        sort(arr);
//
//        System.out.println(Arrays.toString(arr));
        int l = 0;
        int r = 6;
        int mid = l + ((r - l) >>> 1);
        System.out.println(mid);
    }


}
